package com.daaij.sixthchapter;


import java.util.Comparator;
import java.util.Iterator;
import java.util.ListIterator;

/**
 * 二叉堆实现
 */
public class BinaryHeap<T>{

    private static final int INIT_SIZE = 32;

    public Object[] array = new Object[INIT_SIZE];
    private Comparator comparator;
    public int currentIndex = -1;//当前最后一个

    public BinaryHeap(){
        comparator = Comparator.naturalOrder();
    }

    public BinaryHeap(Comparator<T> comparator){
        this.comparator = comparator;
    }

    //增加元素
    public void add(T obj){
        if(currentIndex == array.length - 1){
            grow();
        }
        array[++currentIndex] = obj;
        siftUp(currentIndex);
    }

    //要确保移除最后一个元素。保持堆结构
    public T poll(){

        if(currentIndex == -1){
            return null;
        }
        Object first = array[0];
        array[0] = array[currentIndex];
        array[currentIndex] = first;

        percolateDown(0);

        array[currentIndex] = null;
        currentIndex--;

        return (T) first;
    }

    public void sortOneByOne(){
        if(currentIndex == -1){
            return ;
        }
        Object first = array[0];
        array[0] = array[currentIndex];
        array[currentIndex] = first;

        percolateDown(0);
        currentIndex --;
    }

    private void percolateDown(int index) {
        Object first = array[index];
        while(true){

            int child = getLeft(index);
            if(child >= currentIndex){
                break;
            }
            if(child + 1 < currentIndex && comparator.compare(array[child],array[child + 1]) > 0){
                child ++;
            }
            if(comparator.compare(first,array[child]) > 0){
                array[index] = array[child];
                index = child;
            }else{
                break;
            }
        }
        array[index] = first;
    }


    //上滤，下标从0开始，左孩子2n+1,右孩子2n+2，左孩子的父亲（x-1）/2,右孩子的父亲(x-2)/2
    private void siftUp(int index) {
        Object target = array[index];
        int tmp = index;
        int parentIndex = getParentIndex(index);
        if(parentIndex < 0){
            return;
        }
        while(tmp > 0 && comparator.compare(target,array[parentIndex]) < 0){
            //swap(array,tmp,parentIndex);
            array[tmp] = array[parentIndex];
            tmp = parentIndex;
            parentIndex = getParentIndex(parentIndex);
        }
        array[tmp] = target;
    }

    private void swap(Object[] array, int index, int parentIndex) {
        Object tmp = array[index];
        array[index] = array[parentIndex];
        array[parentIndex] = tmp;
    }

    private int getParentIndex(int index) {
        //左孩子的下标一定为奇数
        if(index%2 == 1){
            return (index - 1) /2;
        }
        return (index - 2) /2;
    }

    private int getLeft(int index){
        return index * 2 + 1;
    }

    private int getRight(int index){
        return index << 1+ 2;
    }

    private void grow() {

        Object[] tmp = array;
        array = new Object[array.length * 2];
        System.arraycopy(tmp,0,array,0,tmp.length);

    }


}
